package org.dandsoft.blackbox.utils;

import java.util.Iterator;

/**
 * @author Vilyuzhanin Denis (Fin)
 */
public class BinaryTree<Data> implements Iterable<Data> {
    public final static int LONG_KEY_SIZE = Long.SIZE;
    public final static int DEFAULT_KEY_SIZE = Integer.SIZE;
    public final static int CHAR_KEY_SIZE = Character.SIZE;
    public final static int BYTE_KEY_SIZE = Byte.SIZE;

    private Node root;
    private int keySize = DEFAULT_KEY_SIZE;
    private int hightMask = 0x1 << keySize;
    private long size;
    private long nodesCount;

    public BinaryTree() {
    }

    public BinaryTree(int keySize) {
        this.keySize = keySize;
        this.hightMask = 0x1 << (keySize - 1);
    }

    public synchronized Data put(long key, Data data) {
        if (data == null) {
            return remove(key);
        } else {
            Data oldData = null;
            Node node = findNode(key, true);
            if (checkLast(key)) {
                oldData = (Data) node.zero;
                node.zero = data;
                size++;
            } else {
                oldData = (Data) node.one;
                node.one = data;
                size++;
            }
            return oldData;
        }
    }

    public synchronized Data get(long key) {
        Node node = findNode(key, false);
        if (node != null) {
            if (checkLast(key)) {
                return (Data) node.zero;
            } else {
                return (Data) node.one;
            }
        } else {
            return null;
        }
    }

    public synchronized Data remove(long key) {
        Data oldData = null;
        Node node = findNode(key, false);
        if (node != null) {
            if (checkLast(key)) {
                oldData = (Data) node.zero;
                node.zero = null;
            } else {
                oldData = (Data) node.one;
                node.one = null;
            }
            size--;
            doRemove(node);
        }
        return oldData;
    }

    protected void doRemove(Node node) {
        if (node != root) {
            if (node.zero == null && node.one == null) {
                Node parent = node.parent;
                node.parent = null;
                nodesCount--;
                if (parent != null) {
                    if (parent.zero == node) {
                        parent.zero = null;
                    }
                    if (parent.one == node) {
                        parent.one = null;
                    }
                    doRemove(parent);
                }
            }
        } else if (root.one == null && root.zero == null) {
            root = null;
            nodesCount--;
        }
    }


    private boolean checkLast(long key) {
        //return (key & this.hightMask) == 0;
        return (key & 0x1) == 0;
    }


    protected Node findNode(long key, boolean isPut) {
        if (root == null && isPut) {
            root = newNode(null);
        } else if (root == null && !isPut) {
            return null;
        }

        //long mask = 0x1;
        long mask = hightMask;
        Node current = root;

        for (int level = 0; level < keySize - 1; level++) {
            if ((key & mask) == 0) {
                if (current.zero == null) {
                    if (isPut) {
                        current.zero = newNode(current);
                    } else {
                        return null;
                    }
                }
                current = (Node) current.zero;
            } else {
                if (current.one == null) {
                    if (isPut) {
                        current.one = newNode(current);
                    } else {
                        return null;
                    }
                }
                current = (Node) current.one;
            }
            mask = mask >> 1;
        }
        return current;
    }

    protected Node newNode(Node parent) {
        nodesCount++;
        Node newNode = new Node();
        newNode.parent = parent;
        return newNode;
    }

    public synchronized long getSize() {
        return size;
    }

    public synchronized long getNodesCount() {
        return nodesCount;
    }

    public Iterator<Data> iterator() {
        return new TreeIterator();
    }

    public BinaryTreeIterator<Data> binaryTreeIterator() {
        return new TreeIterator();
    }

    /**
     *
     */
    static class Node {
        public Node parent;
        public Object zero;
        public Object one;
    }

    /**
     *
     */
    static class StackElement {
        public Node node;
        public int usedCount;
    }

    /**
     *
     */
    class TreeIterator implements BinaryTreeIterator<Data> {
        private Object next;
        private long nextKey;
        private Object previous;
        private long previousKey;
        private boolean isZeroReaded;
        private boolean isOneReaded;
        private StackElement[] stack;
        private int level;
        private boolean isFinish;

        TreeIterator() {
            stack = new StackElement[keySize];
            for (int i = 0; i < stack.length; i++) {
                stack[i] = new StackElement();
            }
            stack[0].node = root;
            level = 0;
            findNext();
        }

        private void countKey() {
            nextKey = 0;
            if (next != null) {
                long mask = 0x1;
                for (int i = 0; i < stack.length; i++) {
                    if (stack[i].usedCount == 2) {
                        nextKey = nextKey | mask;
                    }
                    mask = mask << 1;
                }
            }
        }

        public long getKey() {
            return previousKey;
        }

        private void findNext() {
            synchronized (BinaryTree.this) {
                next = null;
                do {
                    if (!moveDown()) {
                        if (!moveUp()) {
                            isFinish = true;
                            return;
                        }
                    }
                } while (level < stack.length && next == null);
                countKey();
            }
        }

        private boolean moveUp() {
            isOneReaded = false;
            isZeroReaded = false;
            if (level > 0) {
                level--;
                return true;
            } else {
                return false;
            }
        }

        private boolean moveDown() {
            if (level >= stack.length - 1) {
                if (stack[stack.length - 1].usedCount == 0) {
                    next = stack[stack.length - 1].node.zero;
                    stack[stack.length - 1].usedCount = 1;
                    return true;
                } else if (stack[stack.length - 1].usedCount == 1) {
                    next = stack[stack.length - 1].node.one;
                    stack[stack.length - 1].usedCount = 2;
                    return true;
                } else {
                    stack[stack.length - 1].usedCount = 0;
                    return false;
                }

            } else {
                if (stack[level].node.zero != null) {
                    if (stack[level].usedCount == 0) {
                        stack[level].usedCount = 1;
                        stack[level + 1].node = (Node) stack[level].node.zero;
                        stack[level + 1].usedCount = 0;
                        level++;
                        return true;
                    }
                } else {
                    //пропускаем обработку этой ветки так как она пустая
                    stack[level].usedCount = 1;
                }

                if (stack[level].node.one != null) {
                    if (stack[level].usedCount == 1) {
                        stack[level].usedCount = 2;
                        stack[level + 1].node = (Node) stack[level].node.one;
                        stack[level + 1].usedCount = 0;
                        level++;
                        return true;
                    }
                } else {
                    stack[level].usedCount = 2;
                }
                return false;
            }
        }


        public boolean hasNext() {
            return next != null;
        }

        public Data next() {
            if (!isFinish) {
                Data data = (Data) next;
                previous = next;
                previousKey = nextKey;
                findNext();
                return data;
            } else {
                return null;
            }
        }

        public void remove() {

        }
    }


    public static void main(String[] args) {
        int n = 32;
        int elements = 0;
        for (int i = 0; i < n; i++) {
            elements += Math.pow(2, i);
        }

        System.out.println("Elements: " + elements);
    }

}
